package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 29. 两数相除
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 * <p>
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 * <p>
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: dividend = 10, divisor = 3
 * 输出: 3
 * 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
 * 示例 2:
 * <p>
 * 输入: dividend = 7, divisor = -3
 * 输出: -2
 * 解释: 7/-3 = truncate(-2.33333..) = -2
 *
 * @author: cuihao
 * @create: 2020-07-03 01:56
 **/
public class Divide {

    public static void main(String[] args) {
        Divide divide = new Divide();
        System.out.println(divide.divide(2147483647, 2));
    }


    /**
     * 推荐解法 看不懂这个解法
     * 时间复杂度为 logN
     *
     * @param dividend
     * @param divisor
     * @return
     */
    // dividend / divisor
    public int divide0(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }

        // 一般情况，使用类二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        boolean rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }

        List<Integer> candidates = new ArrayList<Integer>();
        candidates.add(divisor);
        int index = 0;
        // 注意溢出
        // 往列表里填充。 已 100/3 为例。列表存储 3,6,12,24,48
        while (candidates.get(index) >= dividend - candidates.get(index)) {
            int temp = candidates.get(index);
            candidates.add(temp + temp);
            ++index;
        }
        int ans = 0;

        // 从最后一个开始处理
        for (int i = candidates.size() - 1; i >= 0; --i) {
            if (candidates.get(i) >= dividend) {
                // << 1 相当于乘以2
                // << 2 相当于乘以4
                // TODO 啥意思？？？
                ans += 1 << i;
                dividend = dividend - candidates.get(i);
            }
        }

        return rev ? -ans : ans;
    }


    /**
     * 这个解法时间复杂度很高
     * <p>
     * dividend/divisor
     *
     * @param dividend
     * @param divisor
     * @return
     */
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        if (divisor == 1) return dividend;
        if (divisor == -1) {
            if (dividend > Integer.MIN_VALUE) {
                return -dividend;// 只要不是最小的那个整数，都是直接返回相反数就好啦
            }
            return Integer.MAX_VALUE;// 是最小的那个，那就返回最大的整数啦
        }
        long a = dividend;
        long b = divisor;
        int sign = 1;
        if ((a > 0 && b < 0) || (a < 0 && b > 0)) {
            sign = -1;
        }
        a = a > 0 ? a : -a;
        b = b > 0 ? b : -b;
        long res = div(a, b);
        if (sign > 0) {
            return res > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) res;
        }

        return (int) -res;

    }

    long div(long a, long b) {  // 似乎精髓和难点就在于下面这几句
        // a / b
        if (a < b) return 0;
        long count = 1;
        long tb = b; // 在后面的代码中不更新b
        while ((tb + tb) <= a) {
            count = count + count; // 最小解翻倍
            tb = tb + tb; // 当前测试的值也翻倍
        }
        return count + div(a - tb, b);
    }

}
